package company.tree;

import java.util.*;

/**
 * 2叉树的删除操作
 * <p>
 * 删除节点思路如下：
 * 节点删除一般可以分为以下三种情况：
 * （1）删除叶子节点（4,7,13）
 * （2）不删除叶子节点，删除带有一个叶子节点的树结点（14）
 * （3）删除带有两个叶子节点的树节点（8,3,6）
 * 第一种 删除方法最简单
 * 设立要删除的节点为targetNode;
 * 找到要删除的节点的父节点parent
 * 判断是父节点的左子树还是右子树
 * 根据节点删除方法：parent.left = null;parent.right = null
 * <p>
 * 第二种 删除方法稍微有点复杂
 * 先找到要删除的节点targetNode;
 * 找到要删除的节点的父节点parent;
 * 判断targetNode的子节点是左子树还是右子树；
 * 判断是父节点的左子树还是右子树;
 * 如果 targetNode下面是左子节点，且：
 * 如果targetNode是parent的左子节点-----parent.left = targetNode.left;
 * 如果targetNode是parent的右子节点-----parent.right = targetNode.left;
 * 如果 targetNode下面是右子节点，且：
 * 如果targetNode是parent的左子节点-----parent.left = targetNode.right;
 * 如果targetNode是parent的右子节点-----parent.right = targetNode.right;
 * <p>
 * <p>
 * 第三种 最复杂：
 * 需要删除有两个子树的节点
 * 先找到要删除的节点targetNode;
 * 找到要删除的节点的父节点parent;
 * 从targetNode的右子树找到最小节点；
 * 设临时变量temp,将最小节点的值保存
 * 删除最小节点
 */
public class BinaryTree {
    TreeNode root;
    Map<String, TreeNode> map = new HashMap<>();

    public static void main(String[] args) {
        // 构建有序二叉树 左<中<右
        BinaryTree tree1 = new BinaryTree();
        /*tree1.insertBinaryTree(tree1.root, 8);
        tree1.insertBinaryTree(tree1.root, 3);
        tree1.insertBinaryTree(tree1.root, 10);
        tree1.insertBinaryTree(tree1.root, 1);
        tree1.insertBinaryTree(tree1.root, 6);
        tree1.insertBinaryTree(tree1.root, 14);
        tree1.insertBinaryTree(tree1.root, 4);
        tree1.insertBinaryTree(tree1.root, 7);
        tree1.insertBinaryTree(tree1.root, 13);
        delBinaryTreeNode(tree1.root, 3);
        infixOrder(tree1.root);*/
        /*String[] nodes = {"1", "3", "null", "null", "2"};
        tree1.root = new TreeNode(1);
        tree1.packTree(tree1.root, nodes);
        tree1.infixOrder(tree1.root);*/
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("\\s+");
        String[] node = input[0].replace("[", "").
                replace("]", "").replace("\\s+", "").split(",");
        String key = input[1].replace("\\s+", "");
        Tree tree = new Tree();
        tree.root = tree.packTree(tree.root, node);
        delBinaryTreeNode(tree.root, Integer.parseInt(key));
        System.out.println(tree.levelPrint(tree.root));

    }

    //递归构建有序二叉树 左<中<右
    public void insertBinaryTree(TreeNode treeNode, int value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
            return;
        }

        if (treeNode.getValue() > newNode.getValue()) {
            if (treeNode.getLeft() == null) {
                treeNode.setLeft(newNode);
            } else {
                insertBinaryTree(treeNode.getLeft(), value);
            }
        } else {
            if (treeNode.getRight() == null) {
                treeNode.setRight(newNode);
            } else {
                insertBinaryTree(treeNode.getRight(), value);
            }
        }
    }

    // 非递归方式 知道根节点，配置子节点
    public TreeNode packBinaryTree(TreeNode treeNode, String[] nodes) {
        int len = nodes.length;
        for (int i = 1; i < len; i++) {
            treeNode = root;
            while (treeNode != null) {
                TreeNode left = treeNode.getLeft();
                TreeNode right = treeNode.getRight();
                int val = Integer.parseInt(nodes[i]);
                TreeNode childNode = new TreeNode(val);
                if (val < treeNode.getValue()) {
                    if (left == null) {
                        treeNode.setLeft(childNode);
                        break;
                    }
                    treeNode = left;
                } else {
                    if (right == null) {
                        treeNode.setRight(childNode);
                        break;
                    }
                    treeNode = right;
                }
            }
        }
        return treeNode;
    }

    // 按照给出来的顺序构建树（当作一般树来构建）
    public TreeNode packTree(TreeNode treeNode, String[] node) {
        // 根节点
        if (treeNode == null) {
            treeNode = new TreeNode(Integer.parseInt(node[0]));
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        int idx = 0;
        int len = node.length;
        while (++idx < len) {
            // 取出父节点
            TreeNode poll = deque.poll();

            // 处理左子树
            if (poll.getLeft() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode left = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setLeft(left);
                    deque.offer(left);
                }
            }
            ++idx;

            // 处理右子树
            if (idx < len && poll.getRight() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setRight(right);
                    deque.offer(right);
                }
            }
        }
        return treeNode;
    }


    /**
     * 2叉搜索树插入指定节点
     * 非递归方式
     *
     * @param treeNode 节点
     * @param value    要插入的节点
     */
    public void insertBinaryTreeNode(TreeNode treeNode, int value) {
        if (treeNode == null) {
            treeNode = new TreeNode(value);
            return;
        }
        while (treeNode != null) {
            if (value > treeNode.getValue()) {
                if (treeNode.getRight() == null) {
                    treeNode.setRight(new TreeNode(value));
                    return;
                }
                treeNode = treeNode.getRight();
            }
            if (value < treeNode.getValue()) {
                if (treeNode.getLeft() == null) {
                    treeNode.setLeft(new TreeNode(value));
                    return;
                }
                treeNode = treeNode.getLeft();
            }
        }
    }

    /**
     * 2叉搜索树查找指定节点
     * 递归方式
     *
     * @param treeNode 节点
     * @param value    要删除的点
     */
    private static TreeNode searchBinaryTreeNode(TreeNode treeNode, int value) {
        if (null == treeNode || treeNode.getValue() == value) {
            return treeNode;
        }
        if (value > treeNode.getValue()) {
            return searchBinaryTreeNode(treeNode.getRight(), value);
        }
        return searchBinaryTreeNode(treeNode.getLeft(), value);
    }

    /**
     * 查找指定节点
     * 非递归方式
     *
     * @param root
     * @param val
     * @return
     */
    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        while (root != null) {
            if (root.getValue() == val) {
                return root;
            }
            if (val < root.getValue()) {
                root = root.getLeft();
            } else {
                if (val > root.getValue()) {
                    root = root.getRight();
                }
            }
        }
        return root;
    }

    private static TreeNode searchParent(TreeNode treeNode, int value) {
        if (treeNode.getLeft() != null && treeNode.getLeft().getValue() == value ||
                treeNode.getRight() != null && treeNode.getRight().getValue() == value) {
            return treeNode;
        }
        if (treeNode.getValue() > value) {
            return searchParent(treeNode.getLeft(), value);
        }
        return searchParent(treeNode.getRight(), value);
    }

    /**
     * 2叉搜索树删除指定节点
     * 删除节点思路如下：
     * 节点删除一般可以分为以下三种情况：
     * （1）删除叶子节点
     * 1、找到指定节点
     * 2、将指定节点置空
     * （2）不删除叶子节点，删除带有一个叶子节点的树结点
     * (其实就是直接用删除节点的子节点替补删除节点位置)
     * 先找到要删除的节点targetNode;
     * 找到要删除的节点的父节点parent;
     * 判断targetNode的子节点是左子树还是右子树；
     * 判断是父节点的左子树还是右子树;
     * 如果 targetNode下面是左子节点，且：
     * 如果targetNode是parent的左子节点-----parent.left = targetNode.left;
     * 如果targetNode是parent的右子节点-----parent.right = targetNode.left;
     * 如果 targetNode下面是右子节点，且：
     * 如果targetNode是parent的左子节点-----parent.left = targetNode.right;
     * 如果targetNode是parent的右子节点-----parent.right = targetNode.right;
     * <p>
     * （3）删除带有两个叶子节点的树节点
     * 第三种 最复杂：
     * 需要删除有两个子树的节点
     * 先找到要删除的节点targetNode;
     * 找到要删除的节点的父节点parent;
     * 从targetNode的右子树找到最小节点；
     *
     * @param treeNode 节点
     * @param value    要删除的点
     */
    private static void delBinaryTreeNode(TreeNode treeNode, int value) {
        if (treeNode == null) {
            return;
        }

        // 找到删除节点
        TreeNode delNode = searchBinaryTreeNode(treeNode, value);
        if (delNode == null) {
            return;
        }

        //如果们发现当前这颗二叉排序树只有一个节点
        if (treeNode.getLeft() == null && treeNode.getRight() == null) {
            treeNode = null;
        }

        // 找到这个节点的父节点
        TreeNode parentNode = searchParent(treeNode, value);

        // 1) 删除节点是叶子节点
        if (delNode.getLeft() == null && delNode.getRight() == null) {
            if (parentNode.getLeft() != null && parentNode.getLeft().getValue() == value) {
                parentNode.setLeft(null);
            }
            if (parentNode.getRight() != null && parentNode.getRight().getValue() == value) {
                parentNode.setRight(null);
            }
        } else if (delNode.getLeft() != null && delNode.getRight() != null) {
            // 2）删除节点有两个子节点
            // 找出右子树最小的节点
            int s = searchRightMinNode(delNode);
            delNode.setValue(s);
        } else {
            //（2）不删除叶子节点，删除带有一个叶子节点的树结点
            TreeNode node = delNode.getLeft() != null ? delNode.getLeft() :
                    delNode.getRight();
            if (parentNode == null) {
                treeNode = node;
            }
            if (parentNode.getLeft() != null &&
                    parentNode.getLeft().getValue() == value) {
                parentNode.setLeft(node);
            } else if (parentNode.getRight() != null &&
                    parentNode.getRight().getValue() == value) {
                parentNode.setRight(node);
            }
        }

    }

    /**
     * 找右子树最小的节点
     *
     * @param treeNode 右节点
     * @return
     */
    private static int searchRightMinNode(TreeNode treeNode) {
        TreeNode target = treeNode.getRight();
        //循环的查找左节点，就会找到最小值
        while (target.getLeft() != null) {
            target = target.getLeft();
        }
        //这时target就指向了最小节点
        //删除最小节点
        delBinaryTreeNode(treeNode, target.getValue());
        return target.getValue();
    }

    //中序遍历
    public void infixOrder(TreeNode treeNode) {
        if (treeNode.getLeft() != null) {
            infixOrder(treeNode.getLeft());
        }
        System.out.println(treeNode.getValue());
        if (treeNode.getRight() != null) {
            infixOrder(treeNode.getRight());
        }
    }
}
